package Sort2;


import java.util.Arrays;
import java.util.Stack;

public class Quick {
    public static void main(String[] args) {
        int[] arr={5,5,3,4,3,4,9,8,1,1,5,4};
//        quick(arr);
        quickLoop(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void quick(int[] arr){
        _quick(arr,0,arr.length-1);
    }

    private static void _quick(int[] arr, int left, int right) {
        if(left>=right){
            return;
        }
        int index=partition(arr,left,right);
        _quick(arr,left,index-1);
        _quick(arr,index+1,right);
    }

    private static int partition(int[] arr, int left, int right) {
        int l=left;
        int r=right;
        int pivot=arr[right];
        while(r>l){
            while(r>l&&arr[l]<=pivot){
                l++;
            }
            while(r>l&&arr[r]>=pivot){
                r--;
            }
            int temp=arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
        }
        int temp=arr[r];
        arr[r]=pivot;
        arr[right]=temp;
        return r;
    }




    public static void quickLoop(int[] arr){
        int left=0;
        int right=arr.length-1;
        Stack<Integer> s=new Stack<Integer>();
        s.push(right);
        s.push(left);
        while(!s.isEmpty()){
            int l=s.pop();
            int r=s.pop();
            if(l>=r){
                continue;
            }
            int index=partition(arr,l,r);
            s.push(r);
            s.push(index+1);
            s.push(index-1);
            s.push(l);
        }
    }
}
